package backtracing;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: june
 * @date: 2023/7/28
 * @description: 93. 复原 IP 地址
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * <p>
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入'.' 来形成。
 * 你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 **/

public class RestoreIpAddress_93 {
    List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        StringBuilder sb = new StringBuilder(s);
        if (s.length() < 4 || s.length() > 12) {
            return result;
        }

        backtrace(sb, 0, 0);
        return result;
    }

    /**
     * @param ip
     * @param startIndex 起始索引
     * @param pointNum   逗点的数量，数量为3时说明已经分割完成了
     */
    private void backtrace(StringBuilder ip, int startIndex, int pointNum) {
        if (pointNum == 3) {
            // 需要再判断第4段是否合法
            if (isValid(ip, startIndex, ip.length() - 1)) {
                result.add(ip.toString());
            }
            return;
        }

        // 切割区间是[startIndex, i]
        for (int i = startIndex; i < ip.length(); i++) {
            if (isValid(ip, startIndex, i)) {
                ip.insert(i + 1, '.');
                backtrace(ip, i + 2, pointNum + 1);
                ip.deleteCharAt(i + 1);
            } else {
                break;
            }
        }
    }

    private boolean isValid(StringBuilder s, int start, int end) {
        // 由于调用isValid()时使用的是i+2，所以会出现 start > end的情况
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && end > start) {
            return false;
        }

        String substring = s.substring(start, end + 1);
        int i = Integer.parseInt(substring);
        if (i < 0 || i > 255) {
            return false;
        }
        return true;
    }


    public static void main(String[] args) {
        RestoreIpAddress_93 restoreIpAddress_93 = new RestoreIpAddress_93();

        List<String> strings = restoreIpAddress_93.restoreIpAddresses("101023");
        System.out.println(strings);

    }
}
